package algorithm.other.LCP20;

import java.util.HashMap;
import java.util.Map;

public class Quick1 {
    public static void main(String[] args) {

    }

    static class Solution {
        final int MOD = 1000000007;
        int target;
        int inc;
        int dec;
        int[] jump;
        int[] cost;
        Map<Long,Long> map = new HashMap<>();
        public int busRapidTransit(int target, int inc, int dec, int[] jump, int[] cost) {
            this.target = target;
            this.inc = inc;
            this.dec = dec;
            this.jump = jump;
            this.cost = cost;
            return (int) (dfs(target) % MOD);

        }

        private long dfs(long target) {
            if(target == 0) return 0;
            if(target == 1) return inc;
            if(map.containsKey(target)) return map.get(target);
            long res = (long) inc * target;
            for(int i = 0; i < jump.length; i++) {
                long modRes = target % jump[i];
                if(modRes == 0) {
                    res = (int) Math.min(res,dfs(target/jump[i]) + cost[i]);
                }else {
                    res = (int) Math.min(res,dfs(target/jump[i]) + cost[i] + (long) inc * modRes) ;
                    res = (int) Math.min(res,dfs(target/jump[i] + 1) + cost[i] + (long) dec * (jump[i] - modRes));
                }
            }
            map.put(target,res);
            return res;
        }
    }
}
